from collections import deque

inf = float('inf')

'''
简单版
'''
def SPFA(n,adj,start):
    dis = [inf] * (1 + n)
    in_queue = [0] * (n + 1)

    dis[start] = 0
    dq = deque()
    in_queue[start] = 1

    while dq:
        o = dq.popleft()
        in_queue[o] = 0
        for nxt,cost in adj[o]:
            if dis[nxt] > dis[o] + cost:
                dis[nxt] = dis[o] + cost
                if not in_queue[nxt]:
                    dq.append(nxt)
                    in_queue[nxt] = 1

    print(*dis)


'''
负环
'''
def SPFA2(n,adj,start):
    cnt = [0] * (n + 1)
    dis = [inf] * (n + 1)
    in_queue = [0] * (n + 1)
    dq = deque()
    dq.append(start)
    in_queue[start] = 0
    while dq:
        o = dq.popleft()
        in_queue[o] = 0
        for nxt,cost in adj[o]:
            if dis[nxt] > dis[o] + cost:
                dis[nxt] = dis[o] + cost
                cnt[nxt]+=1
                # 出现负环
                if cnt[nxt] >=n:return False
                if not in_queue[nxt]:
                    dq.append(nxt)
                    in_queue[nxt] = 1

    return True

